/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/unique-binary-search-trees
   @Language: C++
   @Datetime: 16-02-09 08:49
   */

class Solution {
public:
	/**
	 * @paramn n: An integer
	 * @return: An integer
	 * Tip : catalan number, h(0)=h(1)=1
	 *       h(n) = C(2n,n)/(n+1),
	 *       h(n) = h(n-1)*(4*n-2)/(n+1)
	 */
	int numTrees(int n) {
		// write your code here
		long c=1, i=1;  // 
		for(; i++<n; c=c*(4*i-2)/(i+1));
		return c;
	}
};
